package algorithm;

import java.util.Arrays;

public class QuickSort {
    public static void sort(int[] arr, int left, int right){
        if(left >= right) return;
        int i = left - 1, j = right + 1, base = arr[(left + right) >> 1];
        while(i < j){
            do i++; while (arr[i] < base);
            do j--; while (arr[j] > base);
            if(i < j){
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        sort(arr, left, j);
        sort(arr, j + 1, right);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{-1, 2, -8, -10};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
